二次扫描 换根，难度不大

主要是扫描的时候，方程要对

每扫下一个点的时候，需要把前面的点的牛总数加上这条边，减去后面的点的牛总数乘上这条边

蓝属实有点过了qwq，推P3478，模板题

记得开long long

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
// 尼玛，开个ll记得把这里加多4个3f
#define N 100010
typedef long long ll;
using namespace std;

ll n,x,y,temp;
ll f[N],ans=INF;
ll c[N],qwq[N],size[N];// 尼玛，开个ll不会么
vector<pair<ll,ll>> q[N];

void dfs(ll x,ll fa)
{
    size[x]=c[x];
    for (ll i = 0; i < q[x].size(); i++)
    {
        ll y=q[x][i].first;
        if (y==fa) continue;
        dfs(y,x);//注意先dfs再干别的事
        size[x]+=size[y];
        qwq[x]+=qwq[y]+size[y]*q[x][i].second;
    }
}

void dp(ll x,ll fa)
{
    ll now;
    for (ll i = 0; i < q[x].size(); i++)
    {
        ll y=q[x][i].first;
        if(y==fa)continue;
        f[y]=f[x]-size[y]*q[x][i].second+(size[1]-size[y])*q[x][i].second;
        dp(y,x);
    }
}

int main()
{
    //freopen("P2986_8.in","r",stdin); //提交代码的时候把这个注释掉啊喂
    scanf("%lld",&n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld",&c[i]); //草，下次注意，开了ll记得%d变%lld
    for (ll i = 1; i < n; i++)
    {
        scanf("%d%d%d",&x,&y,&temp);
        q[x].push_back(make_pair(y,temp)); //Get! make_pair(),qwq
        q[y].push_back(make_pair(x,temp));
    }
    dfs(1,0);
    f[1]=qwq[1];
    //cout<<f[1]<<" "<<size[1]<<endl;//提交代码的时候把这个注释掉啊喂
    dp(1,0);
    for (ll i = 1; i <= n; i++)
        ans=min(ans,f[i]); //留个标记，以后尝试吧这个丢到dp里面qwq
    cout<<ans<<endl;
    return 0;

}